#include <stdio.h>



int seq_search(int array[], int n, int k, int seek_seq[]) {
	// 在顺序表array[0..n-1]中查找关键字为k的记录
	// 每次查找都将查找到的位置记录在seek_seq中
	
	int i = 0; // 初始化i=0，从第一个记录开始找
	while (i <n && array[i] != k) { // 顺序查找
		seek_seq[i] = i; // 记录查找到的位置
		i++;
	}
	
	if (i == n) { // 若查找到表尾没找到关键字为k的记录，返回-1
		return -1;
	}
	
	seek_seq[i] = i; // 记录最后一次查找到的位置
	return 0; // 返回查找成功标志
}

void r(int low, int high, int k, int array[], int* G, int seek_seq[], int location) {
	// 在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
	// 无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
	
	if (low > high) { // 未找到，返回-1
		*G = location;
		return;
	}
	
	int mid = (low + high) / 2; // 获取中间位置下标
	
	if (array[mid] == k) { // 找到了，返回0
		seek_seq[location++] = mid; // 纪录查找到的位置
		*G = location;
		return;
	}
	else if (array[mid] > k) { // 关键字比中间记录小，则在左半部分继续查找
		seek_seq[location++] = mid; // 纪录查找到的位置
		r(low, mid - 1, k, array, G, seek_seq, location); // 递归查找左半部分
	}
	else { // 关键字比中间记录大，则在右半部分继续查找
		seek_seq[location++] = mid; // 纪录查找到的位置
		r(mid + 1, high, k, array, G, seek_seq, location); // 递归查找右半部分
	}
}

int bin_search(int array[], int n, int k, int seek_seq[]) {
	// 在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
	// 无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
	
	int G = 0; // 标记查找的位置
	r(0, n - 1, k, array, &G, seek_seq, 0); // 二分查找
	
	if (G == 0) { // G为0说明没有查找到
		return -1;
	}
	
	return 0;
}

int main() {
	int n = 10;
	int array[] = { 0,1,2,3,4,5,6,7,8,9 };
	int seek_seq[10];
	
	for (int i = 0; i <n;  ++i) {
		seek_seq[i] = -1;
	}
	
	int c = seq_search(array, n, 6, seek_seq);
	printf("%d\n", c);
	for (int i = 0; i <n;  ++i) {
		printf("%d,", seek_seq[i]);
	}
	
	for (int i = 0; i <n;  ++i) {
		seek_seq[i] = -1;
	}
	printf("\n");
	
	int d = bin_search(array, n, 4, seek_seq);
	printf("%d\n", d);
	for (int i = 0; i < n; ++i) {
		printf("%d,", seek_seq[i]);
	}
	
	return 0;
}
